package com.ljy.my_study.lintcode.用递归打印数字;

import java.util.ArrayList;
import java.util.List;

/** 
* @author James
* @date 2018年9月29日 
*/
public class TestMain {
//	描述
//	用递归的方法找到从1到最大的N位整数。
//
//	用下面这种方式去递归其实很容易：
//
//	recursion(i) {
//	    if i > largest number:
//	        return
//	    results.add(i)
//	    recursion(i + 1)
//	}
//	但是这种方式会耗费很多的递归空间，导致堆栈溢出。你能够用其他的方式来递归使得递归的深度最多只有 N 层么？
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给出 N = 1, 返回[1,2,3,4,5,6,7,8,9].
//
//	给出 N = 2, 返回[1,2,3,4,5,6,7,8,9,10,11,...,99].
//
//	挑战
//	用递归完成，而非循环的方式。
	public static void main(String[] args) {
//		int n=2;
//		System.out.println((int)Math.pow(10, n-1)*0);
//		for(int i=0;i<=9;i++) {
//			System.out.print((int)Math.pow(10, n-1)*i+",");
//			System.out.print((int)Math.pow(10, n-2)*i+",");
//		}
		System.out.println(numbersByRecursion(1));
	}
	
	public static List<Integer> numbersByRecursion(int n) {
		List<Integer> list=new ArrayList<>();
		if(n==0) {
			return list;
		}
		doNumbersByRecursion(list,0,n);
		list.remove(0);
		return list;
	}
	
	public static void doNumbersByRecursion(List<Integer> list,int num,int n) {
		for(int i=0;i<=9;i++) {
			int num1=0;
			if(n==1) {
				num1=num+i;
				list.add(num1);
			}else {
				num1=num+((int)Math.pow(10, n-1)*i);
				doNumbersByRecursion(list,num1,n-1);
			}
		}
	}
}
